1. Field of the Invention
Intensive efforts are being continually made in the field of electronic digital computers to solve the "programming problem." In this area compilers, or more specifically optimizing compilers, are one of the principle tools utilized to on the one hand make the programmer's task easier and on the other to increase the efficiency of operation of the target CPU. For a very complete treatise on the development of compilers and other language processing systems reference is made to an article entitled "The History of Language Processor Technology in IBM," by F. E. Allen in the IBM Journal of Research and Development, Vol. 25, No. 5, Sept. 1981 on pages 535-548.
Such optimizing compilers conventionally utilize optimization algorithms such as:
Common sub-expression elimination PA1 Moving code out of loops PA1 Eliminating dead code PA1 Strength reduction PA1 Register assignment
Each of these algorithms transforms an intermediate language (IL) program into a semantically equivalent but more efficient IL program. The purpose of these various algorithms is the same as the purpose of the overall compiler i.e. to facilitate the use of very high level source program languages on the input side and to, hopefully, assure that the object program produced by the compiler will run on the target CPU in the most efficient manner possible.
It will be noted in the above list of optimizing approaches, mention is made of working register assignment for allocation to tasks. This is a very important problem as is well known in the computer arts. This is because operations wherein the operands are obtained from and results return to registers can proceed at a much higher speed than those which require memory or storage accessing.
Most compilers assume an arbitrarily large number of registers during their optimization procedures. In fact the result of each different computation in the program is conventionally assigned a different (symbolic) register. At this point a register allocation procedure must be invoked to assign real registers, from those available in the machine, to these symbolic registers. Conventional approaches use a subset of the real registers for special purposes while the remaining set is assigned locally within the statement, or at best the basic block (e.g. a loop). Between these assignments, results which are to be preserved are temporarily stored, and variables are redundantly reloaded. While these approaches clearly work, they are inefficient in that a significant amount of CPU time is wasted while data is being transferred between storage and registers or conversely, data is accessed from and returned to storage directly bypassing the registers completely.
A novel compiler strategy which was significantly different from conventional compilers was described in the literature and specifically referenced in the prior art section, which observed that the register assignment or allocation problem is equivalent to the graph coloring problem, where each symbolic register is a node and the real registers are different colors. When two symbolic registers have the property that there is at least one point in the program when both their values must be retained, that property is modelled on the graph as a vertex or edge between the two nodes. Thus the register allocation problem is equivalent to the problem of coloring the graph so that no two nodes connected by a vertex are colored the same. This is equivalent to saying that each of these two (or more) nodes must be stored in different registers.
This approach has proven very effective. Experience has shown that many procedures "color" so that no store-load operations are necessary to keep results in storage temporarily.
However, a significant shortcoming of the register allocation via coloring procedure referenced above regards the "spilling" problem or the situation where there are more data items to be retained than there are machine registers available. When a spilling problem was found to exist in the above referenced register allocation process the use of the graph coloring analysis approach was abandoned and other ad hoc solutions to the problem were used. While the results of this approach are reasonably good, it requires large amounts of compile time and accordingly a need was recognized for a better approach to the solution of the spilling problem.
2. Prior Art
An article entitled "Register Allocation Via Coloring," by G. J. Chaitin et al, appearing in Computer Languages, Vol. 6, pages 47-57, Pergamon Press, Great Britain, 1981, referred to above, describes the basic concepts of register allocation via coloring but utilizes an entirely different approach to the "spilling" problem. The present invention constitutes a distinct improvement in the area of spilling to that disclosed in this article.
An article entitled "The 801 Minicomputer," by George Radin, published in the ACM SIGPLAN Notices, Vol. 17, No. 4, Apr. 1982, pages 39-47, is an overview of an experimental minicomputer which incorporated an extremely intelligent optimizing compiler utilizing the concepts of register allocation via coloring described in the above-referenced article and which also incorporates the teachings of the present invention.
For a general description of the optimizing compiler itself, reference is made to an article entitled "An Overview of the PL.8 Compiler," by Auslander and Hopkins appearing in the ACM SIGPLAN Notices, Vol. 17, No. 6, June 1982, pages 22-31. Specific reference is made in this article to the present register allocation procedure.
Two articles (1) J. Cocke and P. W. Markstein, "Measurement of Code Improvement Algorithms," in "Information Processing '80," (edited by S. H. Lavington), pages 221-228, North-Holland, Amsterdam, (1980), and (2) F. E. Allen and J. Cocke, "A Program Data Flow Analysis Procedure," Communications ACM 19, pages 137-147 (1976) discuss the objectives and concepts involved in the design of optimizing compilers and provide excellent background material for an understanding of the design approaches utilized in optimizing compilers in which the present invention would have particular utility.
The present register allocation process for use in an optimizing compiler has previously appeared in print as an IBM Research Report No. RC 9124 which was available Nov. 11, 1981, from the library of the Thomas J. Watson Research Center in Yorktown Heights, New York and also appeared in the SIGPLAN '82 Symposium on Compiler Construction, SIGPLAN Notices, Vol. 17, No. 6, June 1982, pages 98-105.